home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / 0989.ZIP / ESPRESSO.ARC / ESPRESSO.C < prev    next >
Text File  |  1987-03-13  |  3KB  |  76 lines
  1. /*
  2.     Module: espresso.c
  3.     Purpose: The main espresso algorithm
  4.  
  5.     Returns a minimized version of the ON-set of a function
  6.  
  7.     The following global variables affect the operation of Espresso:
  8.         trace -- print trace information as the minimization progresses
  9.         remove_essential -- remove essential primes
  10.         single_expand -- if true, stop after very first expand
  11. */
  12.  
  13. #include "espresso.h"
  14.  
  15. pcover espresso(F, D, R)
  16. pcover F, D, R;
  17. {
  18.     pcover E, G, Dsave;
  19.     cost_t cost, best_cost;
  20.     int start, forever = TRUE;
  21.  
  22.     /* Make a copy of D for our own use -- leave original D intact */
  23.     Dsave = D;
  24.     D = sf_save(Dsave);
  25.  
  26.     /* Setup has always been a problem -- unravel and contain here */
  27.     cover_cost(F, &cost);
  28.     if ((cube.part_size[cube.num_vars - 1] > 1) && (cost.out < 5000))
  29.         EXEC(F = sf_contain(unravel(F, cube.num_vars - 1)), "SETUP      ", F);
  30.  
  31.     /* Initial expand and irredundant */
  32.     EXECUTE( F = expand(F, R, FALSE, FALSE), EXPAND_TIME, F);
  33.     EXECUTE( F = irredundant(F, D), IRRED_TIME, F);
  34.     if (single_expand)
  35.         goto skip_loop;
  36.     if (remove_essential && cube.num_binary_vars == cube.num_vars - 1) {
  37.         EXECUTE( E = essential(&F, &D), ESSEN_TIME, E);
  38.     } else
  39.         E = new_cover(0);
  40.     cover_cost(F, &best_cost);
  41.  
  42.     do {
  43.         /* Repeat inner loop until solution becomes "stable" */
  44.         do {
  45.             start = F->count;
  46.             EXECUTE(F = reduce(F, D), REDUCE_TIME, F);
  47.             EXECUTE_BREAK(F = expand(F, R, FALSE, FALSE), EXPAND_TIME, F);
  48.             EXECUTE_BREAK(F = irredundant(F, D), IRRED_TIME, F);
  49.             copy_cost(&cost, &best_cost);
  50.         } while (F->count < start);
  51.  
  52.         /* Perturb solution to see if we can continue to iterate */
  53.         EXECUTE( G = reduce_gasp(F, D), GREDUCE_TIME, G);
  54.         EXECUTE( G = expand_gasp(G, R), GEXPAND_TIME, G);
  55.         EXECUTE_BREAK( F = irred_gasp(F, D, G), GIRRED_TIME, F);
  56.         copy_cost(&cost, &best_cost);
  57.  
  58.     } while (forever);
  59.  
  60.     /* Append the essential cubes to F */
  61.     F = sf_append(F, E);
  62.     if (trace) size_stamp(F, "ADJUST     ");
  63.  
  64.     /* Remove redundant parts from the multiple-valued variables */
  65. skip_loop:
  66.     cover_cost(F, &best_cost);
  67.     do {
  68.         EXECUTE_BREAK( F = mv_reduce(F, Dsave), MV_REDUCE_TIME, F);
  69.         copy_cost(&cost, &best_cost);
  70.         EXECUTE_BREAK( F = expand(F, R, FALSE, TRUE), RAISE_IN_TIME, F);
  71.         copy_cost(&cost, &best_cost);
  72.     } while (force_irredundant);
  73.  
  74.     return F;
  75. }
  76.